#include<vector>
#include<algorithm>
using namespace std;

class Solution {
private:
    int dist(const vector<int>& point) {
        return point[0] * point[0] + point[1] * point[1];
    }
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        if (points.size() <= K)
            return points;
        int left = 0, right = points.size() - 1;
        while (true) {
            int left_old = left, right_old = right;
            int index = left++;
            while (left <= right) {
                while (left <= right && dist(points[left]) <= dist(points[index]))++left;
                while (left <= right && dist(points[right]) > dist(points[index]))--right;
                if(left<=right)
                    swap(points[left], points[right]);
            }
            swap(points[right], points[index]);
            if (right+1 == K)
                break;
            else if (right+1 < K) 
                right = right_old;
            else {
                left = left_old;
            }
        }
        return vector<vector<int>>(points.begin(), points.begin() + K);
    }
};

//class Solution {
//public:
//    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
//        sort(points.begin(), points.end(), [](const vector<int>& left, const vector<int>& right) {
//            return (left[0] * left[0] + left[1] * left[1]) < (right[0] * right[0] + right[1] * right[1]);
//            });
//        return vector<vector<int>>(points.begin(), points.begin() + K);
//    }
//};